package com.linyaonan.leetcode.medium._1026;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
 *
 * （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
 * 输出：7
 * 解释：
 * 我们有大量的节点与其祖先的差值，其中一些如下：
 * |8 - 3| = 5
 * |3 - 7| = 4
 * |8 - 1| = 7
 * |10 - 13| = 3
 * 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
 * 示例 2：
 *
 *
 * 输入：root = [1,null,2,null,0,3]
 * 输出：3
 *
 *
 * 提示：
 *
 * 树中的节点数在 2 到 5000 之间。
 * 0 <= Node.val <= 10^5
 *
 * @author: Lin
 * @date: 2024/4/5
 */
public class MaximumDifferenceBetweenNodeAndAncestor {

    private int result = 0;

    /**
     * 递归思路：由于节点数值全部大于等于0
     * 对于根节点，左子树中的最小值，最大值，右子树最小值，最大值 其中就包括了结果
     * @param root
     * @return
     */
    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);

        return result;
    }

    private void dfs(TreeNode node, int min, int max) {
        if (node != null) {
            min = Math.min(min, node.val);
            max = Math.max(max, node.val);
            result = Math.max(Math.max(Math.abs(node.val - min), Math.abs(node.val - max)), result);

            dfs(node.left, min, max);
            dfs(node.right, min, max);
        }
    }

    /**
     * 递归，将自己的父节点全部传入
     * 有个很明显的问题，大部分节点的判断是重复的，只需要记录最大与最小的数值，这样转换为方法1
     * @param root
     * @return
     */
    public int maxAncestorDiff2(TreeNode root) {
        dfs2(root, new ArrayList<>());

        return result;
    }

    private void dfs2(TreeNode node, List<Integer> parent) {
        if (node != null) {
            int tmp = 0;
            for (Integer i : parent) {
                tmp = Math.max(Math.abs(i - node.val), tmp);
            }
            result = Math.max(result, tmp);


            if (node.left != null) {
                parent.add(node.val);
                dfs2(node.left, parent);
                parent.remove(parent.size() - 1);
            }
            if (node.right != null) {
                parent.add(node.val);
                dfs2(node.right, parent);
                parent.remove(parent.size() - 1);
            }
        }
    }

}
